package com.xw.class12;

/**
 * @author XW
 * @data 2023/8/23 15:41
 * @description 判断一棵树是否是满二叉树  节点数量等于 2^heigh - 1
 */
public class Code04_isFull {
    static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int value){
            this.value = value;
        }
    }

    public static boolean isFull(Node head){
        if(null == head){
            return true;
        }
        Info all = process(head);
        return (1<<all.height-1) == all.nodes;
    }

    private static Info process(Node node) {
        if(null == node ){
            new Info(0,0);
        }
        Info left =process(node.left);
        Info right =process(node.right);
        int height = Math.max(left.height, right.height) + 1;
        int nodes = left.nodes + right.nodes + 1;
       return new Info(height,nodes);
    }

    static class Info{
        public int height;
        public int nodes;
        public Info(int h, int n) {
            height = h;
            nodes = n;
        }
    }
}
